【APIO2011】方格染色 <带权并查集>

Problem

【APIO2011】方格染色

Description

和他的妹妹有一个包含个方格的表格。她们想要将其的每个方格都染成红色或蓝色。
出于个人喜好，他们想要表格中每个的方形区域都包含奇数个（个或个）红色方格。可是昨天晚上，有人已经给表格中的一些方格染上了颜色！
现在和非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍然满足她们的要求。
如果可能的话，满足他们要求的染色方案数有多少呢？

Input

输入的第一行包含三个整数, 和，分别代表表格的行数、列数和已被染色的方格数目。
之后的行描述已被染色的方格。其中第行包含三个整数, 和，分别代表第个已被染色的方格的行编号、列编号和颜色。为表示方格被染成红色，为表示方格被染成蓝色。

Output

输出一个整数，表示可能的染色方案数目模得到的值。

Sample Input

Sample Output

Hint

对于所有的测试数据，, , , 。
数据为国内数据+国际数据+修正版
鸣谢GYZ

标签：带权并查集 异或方程组

Solution

并查集解异或方程组。

令表示第行第列的格子最终是否被染，对于，一定有。而易得到结论：确定一行一列的情况，即可确定最后是否能正确染色。

于是我们尝试确定第一行和第一列的情况，即做一个个变量的异或方程组。
对于给定的，我们如果把的所有上一段所属方程异或起来，那么相同元抵消，可知，如果我们知道，那么就能确定的值，这时用一个带权并查集维护一下，即可得到联通块的个数。那么答案为（所在联通块的取值是一定的）。
如果我们预先不知道的值，就可以枚举两种取值，分别计算后加起来即可。

Code

#include <bits/stdc++.h>
#define MAX_N 200000
#define MOD 1000000000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, k, f[MAX_N+5], g[MAX_N+5];
int x[MAX_N+5], y[MAX_N+5], c[MAX_N+5];
int getf(int x) {return f[x] == x ? x : getf(f[x]), g[x] ^= g[f[x]], f[x] = f[f[x]];}
lnt calc(int val) {
    lnt ret = 1;
    for (int i = 1; i <= k; i++) if (x[i] > 1 && y[i] > 1) c[i] ^= val;
    for (int i = 1; i <= n+m; i++) f[i] = i, g[i] = 0; f[n+1] = 1;
    for (int i = 1; i <= k; i++) if ((x[i]^1) || (y[i]^1)) {
        int u = getf(x[i]), v = getf(y[i]+n), w = g[x[i]]^g[y[i]+n]^c[i];
        if (u^v) f[v] = u, g[v] = w; else if (w) return 0LL;
    }
    for (int i = 1, t = 0; i <= n+m; i++) if (getf(i) == i)
        {if (t) (ret *= 2LL) %= MOD; else t = 1;}
    return ret;
}
int main() {
    read(n), read(m), read(k);
    bool f0 = true, f1 = true; lnt ans = 0;
    for (int i = 1; i <= k; i++) {
        read(x[i]), read(y[i]), read(c[i]);
        if (!(x[i]%2) && !(y[i]%2)) c[i] ^= 1;
        if (x[i] == 1 && y[i] == 1) c[i] ? f0 = false : f1 = false;
    }
    if (f0) (ans += calc(0)) %= MOD;
    if (f1) (ans += calc(1)) %= MOD;
    return printf("%lld\n", ans), 0;
}